home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / hzip.com / README < prev   
Encoding:
Text File  |  1991-01-08  |  3.7 KB  |  108 lines
  1.                          HZIP README FILE
  2.  
  3.                          January 8, 1991
  4.  
  5. DESCRIPTION
  6. -----------
  7.  
  8. The HZIP program and associated files implements an algorithm for
  9. generating length-limited huffman codes, to be used in compressing
  10. files. Limiting the codes to a known length is useful because
  11. you can then pack the codes into known size words. For instance,
  12. as given here, you can guarantee codes <= 16 bits, which means
  13. the codes can be stored in two-byte words. Without such length
  14. limiting, there's no guarantee that the codes would fit.
  15.  
  16. The algorithm used is called the Package-Merge algorithm as described
  17. in the paper "A Fast Algorithm for Optimal Length-Limited Huffman
  18. Codes", Lawrence L. Larmore and Daniel S. Hirschberg, JACM, 
  19. Vol. 37, No.3, July 1990, pp. 464-473.
  20.  
  21. This code is my interpretation of the algorithm, (it's presented
  22. rather abstractly in the paper). I hope I got it right.
  23.  
  24. The straight-forward implementation of the algorithm consumes
  25. lots of memory and takes a fair amount of time. This implementation
  26. has been optimized as much as I know how, reducing the memory usage
  27. of the algorithm itself from over 200k, to around 64k, and speeding
  28. up the algorithm by at least double over the initial attempt. 
  29.  
  30. The authors Larmore and Hirschberg describe a modified algorithm
  31. which uses much less space, but they don't give the full algorithm
  32. and I couldn't make heads or tails out of what they did give. If 
  33. anyone knows an implementation of this improved algorithm, I'd like
  34. to see it.
  35.  
  36. The source code given is written in Turbo C++ 1.01. Project
  37. files are supplied to make it easy to re-compile the code.
  38.  
  39.  
  40. COPYRIGHT NOTICE
  41. ----------------
  42.  
  43. The source code and associated files, as given in CONTENTS section
  44. is COPYRIGHT (c) 1991 AZARONA SOFTWARE. ALL RIGHTS RESERVED.
  45.  
  46. The source code as given here is FREEWARE. That means you may use
  47. it in your own projects without charge. HOWEVER, THE SOFTWARE IS NOT
  48. PUBLIC DOMAIN. That means the copyright is still in effect, (which 
  49. means YOU can't copyright it), and means that if you do use the 
  50. source code, you must keep the embedded copyright notices intact.
  51. It also means YOU CAN'T CHARGE ANYONE ELSE TO USE THE CODE. Plus,
  52. if you give away the code, you must include all the files mentioned
  53. in the CONTENTS section, including this readme file.
  54.  
  55. If you find a smaller, faster way to implement the package-merge
  56. algorithm, I'd like to hear about it.
  57.  
  58.  
  59. CONTENTS
  60. --------
  61.  
  62. You should have the following files:
  63.  
  64.   readme.txt  - This file
  65.   hzip.exe    - Huffman compressor
  66.   hunzip.exe  - Huffman decompressor
  67.   hzip.prj    - Project file for huffman compressor
  68.   hunzip.prj  - Project file for huffman decompressor
  69.   hzip.cpp    - Source to huffman compressor
  70.   hunzip.cpp  - Source to huffman decompressor
  71.   pnode.h     - Package node header file
  72.   pnode.cpp   - Package node source code
  73.   pkmg.h      - Package-merge algorithm header file
  74.   pkmg.cpp    - Package-merge algorithm source file
  75.   huffenc.h   - Huffman encoder header file
  76.   huffenc.cpp - Huffman encoder source file
  77.   huffdec.h   - Huffman decoder header file
  78.   huffdec.cpp - Huffman decoder source file
  79.  
  80.  
  81. RESTRICTIONS
  82. ------------
  83.  
  84. The implementation given here is limited to a algoritm size
  85. of 4096. (The size of the algorithm is number of symbols *
  86. max number of levels. EG: 256 symbols by 16 levels, which
  87. would give you enough space for coding the 256 extended 
  88. character set into 16-bit words.) Also, the maximum number
  89. of symbols is 256.
  90.  
  91.  
  92. CONTACTING THE AUTHOR
  93. ---------------------
  94.  
  95. You may reach me at the following U.S. Mail and CompuServe
  96. e-mail addresses:
  97.  
  98.    Bryan Flamig
  99.    Azarona Software
  100.    P.O. Box 13433
  101.    Denver, CO  80201
  102.  
  103.    Compuserve: 73057,3172
  104.  
  105.  
  106.  
  107.  
  108.